package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         304,
		Discription: "O(1)时间返回子矩阵之和",
		Level:       2,
		Labels: map[string]int{
			"前缀和":  1,
			"动态规划": 1,
			"矩阵":   1,
		},
	})
}

type NumMatrix struct {
	prefix [][]int
}

func Constructor8(matrix [][]int) NumMatrix {
	m := len(matrix)
	n := len(matrix[0])
	pre := make([][]int, m)
	for i := range pre {
		pre[i] = make([]int, n)
	}
	pre[0][0] = matrix[0][0]
	for i := 1; i < m; i++ {
		pre[i][0] = pre[i-1][0] + matrix[i][0]
	}
	for j := 1; j < n; j++ {
		pre[0][j] = pre[0][j-1] + matrix[0][j]
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
            //[0...i][0...j]范围内的前缀和
			pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i][j]
		}
	}

	return NumMatrix{
		prefix: pre,
	}
}

func (matrix *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	res := matrix.prefix[row2][col2]
    //注意判断边界
	if col1 >= 1 {
		res -= matrix.prefix[row2][col1-1]
	}

	if row1 >= 1 {
		res -= matrix.prefix[row1-1][col2]
	}

	if row1 >= 1 && col1 >= 1 {
		res += matrix.prefix[row1-1][col1-1]
	}


	return res
}
